/*
题目: 相似度为 k 的字符串
对于某些非负整数 k ，如果交换 s1 中两个字母的位置恰好 k 次，能够使结果字符串等于 s2 ，则认为字符串 s1 和 s2 的 相似度为 k 。

给你两个字母异位词 s1 和 s2 ，返回 s1 和 s2 的相似度 k 的最小值。

https://leetcode.cn/problems/k-similar-strings
 */
public class KSimilarity {
    int n ;
    int minn = Integer.MAX_VALUE;

    public int kSimilarity(String s1, String s2) {
        n = s1.length();
        return backTrack(s1, s2, 0, 0);
    }

    private int backTrack(String exp, String tar, int index, int steps) {
        if (steps >= minn)  return minn;

        if (index >= n - 1)
            return minn = Math.min(minn, steps);

        // 外层 for 保证 [0, i) 都是 和 tar 相等的
        for (int i = index; i < n; i ++) {
            if (exp.charAt(i) == tar.charAt(i)) continue ;

            for (int j = i + 1; j < n; j ++) {
                // 如下, 剪枝: 某个位置 不用变化, 同一位置相同的直接跳过
                // a d 'b' b
                // a b 'b' d
                if (tar.charAt(i) == exp.charAt(j) && tar.charAt(j) != exp.charAt(j)) {
                    exp = swap(exp, i, j);

                    minn = Math.min(minn, backTrack(exp, tar, i + 1, steps + 1));
                    exp = swap(exp, i, j);
                }
            }
            return minn;
        }

        return minn = Math.min(minn, steps);
    }

    private String swap(String exp, int a, int b) {
        char[] cs = exp.toCharArray();
        char t = cs[a];
        cs[a] = cs[b];
        cs[b] = t;
        return new String(cs);
    }
}
